An arbiter is a well known interface circuit that controls a communication protocol on the basis of assigning priority to a particular input signal selected from a plurality of input signals in order to determine a processing sequence for the input signals. The priority assignment may be based on temporal aspects of the signals, e.g., the order of arrivals at the arbiter's inputs. Assigning a priority to the particular input signal is then to be understood as selecting the particular input signal on the basis of its temporal characteristics with respect to the temporal characteristics of the other input signals: e.g., the particular input signal is the first to have arrived and determines the further processing. Typically, arbiters are used for controlling the communication between transmitting stations and receiving stations interconnected via a bus system.
U.S. Pat. No. 4,835,422 issued to Dike et al. discusses an electronic arbiter circuit with an input section that provides relative priority signals upon receiving a plurality of input signals. Each respective relative priority signal specifies which one of a respective pair of input signals has gained priority over the other input signal. The relative priority signals associated with all pairs of input signals are supplied to a decode logic circuit. The decode logic circuit operates on the relative priority signals in order to furnish output signals specifying an absolute priority of a particular one of the input signals. That is, the output signals indicate which one of the input signals is considered to have gained priority over all other input signals.
In addition, the decode logic circuit takes care of priority conflicts that may occur at the level of the relative priority signals. A priority conflict is an event wherein, for example, three or more input signals arrive substantially simultaneously within the resolution of the electronics and the delay paths involved. Such an event gives rise to inconsistences. For example, the relative priority signals may indicate that the respective input signals at first, second and third input terminals respectively gained priority over the input signals at the second, third and first input terminals. Assuming that one of these input signals indeed was the first to arrive overall, such a cyclic relationship does not give an unambiguous absolute priority winner. The decode logic circuit is designed to resolve the conflict by selecting in a predetermined manner one of the input signals, which was involved in causing the conflict, as the absolute priority winner.
In the known arbiter, the signal path is from the inputs of the input section through the decode logic circuit to the circuit's outputs. The decode logic circuit itself comprises arrangements of several logic AND gates that receive particular combinations of the relative priority signals to be fed into a single logic OR gate. The size of each AND gate and each OR gate grows with the number of relative priority signals to be processed. For a 4-input arbiter, for instance, four arrangements of three 3-input AND gates with outputs coupled to a 3-input OR gate each are required. A 6-input arbiter designed on the basis of the same philosophy would need four arrangements with twelve 5-input AND gates and a 12-input OR gate each, and two arrangements with eleven 5-input AND gates and an eleven-input OR gate each.
Beyond a certain number of N inputs, it becomes impractical or impossible to use a single logic N-input gate, owing to, for instance, transistor characteristics related to threshold voltages and saturation phenomena. Instead, a combination of logic gates, each with a lower number of inputs, is employed to perform the same logic function. This, however, introduces additional cumulative gate delays. Accordingly, the arbiter's speed decreases as the number of input signals increases. As an illustration, a prior art 4-input arbiter has a typical signal propagation delay of 7 nsec. A 6-input arbiter fabricated in the same technology would have a typical propagation delay of 9 nsec, whereas the propagation delay in a 16-input arbiter typically would be 14 nsec.
The majority of the events to be evaluated by an arbitrary arbiter does not entail priority conflicts. Since in the prior art the single signal path always leads through the conflict-resolving decode logic, unnecessary signal propagation delays are inflicted upon the majority of the priority cases to be examined. The cumulative effect of the delays becomes more pronounced with an increasing number of input signals to be processed due to the increased number of combined logic gates, as explained above.
Another undesirable aspect of the architecture of the prior art arbiter is that the output signals, which are indicative of the absolute priority of a particular input signal, may change if one or more input signals, other than the particular input signal, switch. Both switching of an input signal with a lower priority and the operation of the decode logic will resolve a priority conflict. Switching of a lower priority signal may change the status of the decode logic and, therefore, the output signals.